L.DistanceGrid = function (cellSize) {
    this._cellSize = cellSize;
    this._sqCellSize = cellSize * cellSize;
    this._grid = {};
    this._objectPoint = {};
};

L.DistanceGrid.prototype = {

    addObject: function (obj, point) {
        var x = this._getCoord(point.x),
            y = this._getCoord(point.y),
            grid = this._grid,
            row = grid[y] = grid[y] || {},
            cell = row[x] = row[x] || [],
            stamp = L.Util.stamp(obj);

        this._objectPoint[stamp] = point;

        cell.push(obj);
    },

    updateObject: function (obj, point) {
        this.removeObject(obj);
        this.addObject(obj, point);
    },

    //Returns true if the object was found
    removeObject: function (obj, point) {
        var x = this._getCoord(point.x),
            y = this._getCoord(point.y),
            grid = this._grid,
            row = grid[y] = grid[y] || {},
            cell = row[x] = row[x] || [],
            i, len;

        delete this._objectPoint[L.Util.stamp(obj)];

        for (i = 0, len = cell.length; i < len; i++) {
            if (cell[i] === obj) {

                cell.splice(i, 1);

                if (len === 1) {
                    delete row[x];
                }

                return true;
            }
        }

    },

    eachObject: function (fn, context) {
        var i, j, k, len, row, cell, removed,
            grid = this._grid;

        for (i in grid) {
            row = grid[i];

            for (j in row) {
                cell = row[j];

                for (k = 0, len = cell.length; k < len; k++) {
                    removed = fn.call(context, cell[k]);
                    if (removed) {
                        k--;
                        len--;
                    }
                }
            }
        }
    },

    getNearObject: function (point) {
        var x = this._getCoord(point.x),
            y = this._getCoord(point.y),
            i, j, k, row, cell, len, obj, dist,
            objectPoint = this._objectPoint,
            closestDistSq = this._sqCellSize,
            closest = null;

        for (i = y - 1; i <= y + 1; i++) {
            row = this._grid[i];
            if (row) {

                for (j = x - 1; j <= x + 1; j++) {
                    cell = row[j];
                    if (cell) {

                        for (k = 0, len = cell.length; k < len; k++) {
                            obj = cell[k];
                            dist = this._sqDist(objectPoint[L.Util.stamp(obj)], point);
                            if (dist < closestDistSq ||
                                dist <= closestDistSq && closest === null) {
                                closestDistSq = dist;
                                closest = obj;
                            }
                        }
                    }
                }
            }
        }
        return closest;
    },

    _getCoord: function (x) {
        var coord = Math.floor(x / this._cellSize);
        return isFinite(coord) ? coord : x;
    },

    _sqDist: function (p, p2) {
        var dx = p2.x - p.x,
            dy = p2.y - p.y;
        return dx * dx + dy * dy;
    }
};
